package com.xzz.number;

import java.util.HashMap;
import java.util.LinkedList;

/**
 * @author: hhz
 * @create: 2022-02-09 17:35
 * 2006. 差的绝对值为 K 的数对数目
 **/
public class CountKDifference {
    public static void main(String[] args) {
        System.out.println(countKDifference(new int[]{1, 2, 2, 1}, 1));

        System.out.println(countKDifference(new int[]{1, 3}, 3));

        System.out.println(countKDifference(new int[]{3,2,1,5,4}, 2));
    }
    public static int countKDifference(int[] nums, int k) {
        int[] cnts = new int[110];
        int n = nums.length, ans = 0;
        for (int i = 0; i < n; i++) {
            int t = nums[i];
            if (t - k >= 1) ans += cnts[t - k];
            if (t + k <= 100) ans += cnts[t + k];
            cnts[t]++;
        }
        return ans;

    }
    public static int countKDifference2(int[] nums, int k) {
        int res = 0;
        HashMap<Integer, LinkedList<Integer>> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (map.containsKey(num)) {
                LinkedList<Integer> list = map.get(num);
                list.add(i);
                map.put(num, list);
            } else {
                LinkedList<Integer> list = new LinkedList<>();
                list.add(i);
                map.putIfAbsent(num, list);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            int num1 = num - k;
            LinkedList<Integer> list = map.getOrDefault(num1, new LinkedList<>());
            if (!list.isEmpty()) {
                for (Integer integer : list) {
                    if (integer > i) {
                        res++;
                    }
                }
            }

            int num2 = num + k;
            LinkedList<Integer> list2 = map.getOrDefault(num2, new LinkedList<>());
            if (!list2.isEmpty()) {
                for (Integer integer : list2) {
                    if (integer > i) {
                        res++;
                    }
                }
            }
        }
        return res;
    }
}
